1. Field of Invention
The invention relates to error correction decoding. More particularly, the present invention relates to error correction decoding based on the syndrome decoding scheme, which means the set of all syndromes is one-to-one correspondent to the set of all correctable error patterns. Examples using this scheme include linear codes, cyclic codes, etc.
2. Description of Related Art
Error correction coding plays an important role in the digital era since data transmission over a channel is prone to errors due to factors such as fading, channel noise and signal interference. Errors can happen in any communication channels. Because of this, a corrupted form of the transmitted signal will be obtained in the receiver. By using the error-correcting coding, correctable errors will be eliminated and the original transmitted signal will be recovered without the request of re-sending the signals.
The underlying principle of all of these schemes is to add redundancy to the original information message such that the errors during transmission may be detected and corrected. The schemes select a codeword for every message-word to be transmitted. The selected codeword represents the data of the message-word and additionally has a redundant data component, which is used for error-control. The amount of redundancy added is a function of the error-control capability of the scheme. At the receiver, a corrupted form of the transmitted codeword is received, and this corrupted form is called a corrupted codeword. However, if the errors in the corrupted codeword are within the error-control capability of the scheme, the receiver can determine the correct message-word corresponding to the corrupted codeword.
The decoding procedures to remove an error pattern from the corrupted codeword involve the following steps. First, a syndrome corresponding to the corrupted codeword is calculated. The syndrome is the characteristic of the error pattern hiding in the corrupted codeword. Hence, the syndrome is used to identify the error pattern hiding in the corrupted codeword through a decoding process. Once the error pattern is identified, a corresponding correction is applied to the corrupted codeword to remove the error and obtain the original transmitted codeword.
A variety of decoding schemes have been proposed to perform error correction. However, a major drawback of the existing decoding methods is the amount of computing time spent in the decoding process, which makes it difficult to be implemented in the real-time applications. There are two major reasons why these decoding methods are that time-consuming: first, the algebraic computations involved are quite complicated in determining the error pattern; second, some decoding procedures are executed recursively several times.
Thus, there is a need for a faster and simpler error correction decoding scheme, which provides high-speed performance and fits the requirement of most major applications.